package com.arron.algorithm.sort;


/**
 * 希尔排序
 * 相当于插入排序的改装版
 */
public class ShellSort {


    public static void main(String[] args) {
        int[] array={35,63,48,9,86,24,53,72,1,93,43,37,18,16};
        sort(array);
    }


    public static void sort(int[] array){

        int len = array.length;
        //每轮循环的增量
        int gap = len/2;
        int j= 0; //记录已经有序的位置下标
        int current = 0;//记录移动的元素
        while (gap>0) {
            for (int i = gap; i < len; i++) {
                current = array[i];
                for (j = i - gap; j >= 0; j -= gap) {
                    if (array[j] > current) {
                        //如果
                        array[j + gap] = array[j];

                    } else {
                        //找到合适的位置插入
                        break;
                    }
                }
                //跳出循环说明找到了合适的插入位置
                array[j + gap] = current;
            }
            System.out.println("本轮增量 gap = " + gap + "排序后的数组：");
            print(array);
            gap /= 2;
        }

    }

    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }



}
